Field of the Invention
This invention relates to a method and system for sending and controlling streaming interactive content comprising prefetched packets of geometric, lighting, and other information which is rendered by a receiving device.
Description of Background
The method of transmitting interactive content as single-frame packets of geometry, texture, lighting and other data which is rendered in real-time on a client or receiver device is described in U.S. Pat. Nos. 6,057,847 and 6,111,582. In these methods the single-frame packets are generated in real-time using the method of primitive reprojection.
The method of transmitting interactive content as prefetched packets of geometry, texture, and other information, in which the prefetched packets correspond to delta-PVS (potentially visible set), also called visibility event information, is described in the PCT patent application number PCT/US2011/042309, the entire contents of which are incorporated herein by reference. In this method, the packets contain information representing newly visible graphic elements as well as information indicating newly occluded graphic elements. This information is organized as delta-PVS or visibility event packets, wherein each packet contains information reflecting graphics elements that become potentially newly visible or newly invisible as a viewpoint moves from one viewcell to another. In this method, the packets are not generated in real-time but instead pre-computed using a method of from-viewcell visibility precomputation, and related methods of compression to encode the packets. At runtime, the packets are prefetched to the client rendering device using navigation-based speculative prefetch driven by the viewer's current and predicted viewpoint location in a set of viewcells that represent navigable regions of a model. Together, the methods of PCT patent application number PCT/US2011/042309 comprise an efficient codec for the streaming delivery of interactive content such as video games.
The codec of PCT patent application number PCT/US2011/042309 can also deliver content that is not necessarily interactive. In this use of the codec, camera position and direction is not interactively controlled by the user, but is determined by one or more scripted camera motion paths. This approach allows the codec to deliver scripted, non-interactive content which, of course, may include animated characters and other scripted dynamic effects. Applied in this way, the codec streams content that effectively corresponds to a conventional, non-interactive animated sequence. As detailed in PCT patent application number PCT/US2011/042309, this codec can deliver the information used to generate the corresponding image sequence at very high resolutions using a lower bandwidth to directly transmitting the image sequence using image-based codecs such as MPEG-4 or the real-time image compression method used by the OnLive corporation.
Broadband digital service providers such as cable and satellite television companies constantly seek ways to increase the amount of content that they can deliver using the bandwidth that is available. The codec of PCT patent application number PCT/US2011/042309, when delivering a unidirectional data stream driven by a scripted camera motion path as previously described, can be used to deliver the same compelling story, visual, and audio experience as conventional high-def video, but at a lower bandwidth than video.
Most adults do not play modern shooter or action games such as Call of Duty Modern Warfare 2, Assassin's Creed, Crysis, Bioshock 2 etc. Yet these types of games can often provide a compelling story, visual and audio experience that focus groups of older adults enjoy watching. But in their pure game form, this content often demands too much interaction and can be tiring to play to completion or even to the next “level” or episode of the game.
Thus, there is a need for an efficient content delivery method which provides conventional, non-interactive or passive high-definition video experience while providing viewers the option of switching between the passive video-like experience and an interactive game-like experience on-demand.
Prefetch is a general method of data delivery which hides latency or improves hit rate by pre-sending data to a client unit before it is actually needed by the client unit. As specified in the co-pending application PCT patent application number PCT/US2011/042309, in the context of visibility event data streaming, specific prefetch methods are used to decrease the chance of late packet arrival which would otherwise cause noticeable visibility errors during the streamed visualization.
In general, regardless of the application, prefetch increases the amount of data streamed, since inevitably more data is delivered to a client unit than will actually be used. Rules and algorithms for optimal prefetching and caching in general applications are given by Pei Cao, (Cao, P, Application-Controlled File Caching and Prefetching. PhD Dissertation, Princeton University, January, 1996, the entire contents of which are incorporated herein by reference.) Cao's aggressive and conservative prefetch algorithms provide methods of minimizing the elapsed time of a known sequence of references.
Wu et al. (Wu, B., Kshemkalyani, D., Object-Greedy Algorithms for Long-Term Web Prefetching, Proceedings of the IEEE Conference on Network Computing and Applications, 2004 pp. 61-68, the entire contents of which are incorporated herein by reference) has developed an algorithm which provides a local solution for prefetching, which balances the increased hit rate benefit of prefetching with the cost of increased bandwidth consumption incurred by prefetch of long-term general-purpose web page content.
In 2003, Chim et al. (Jimmy Chim, Rynson W. H. Lau, Hong Va Leong, and Antonio Si, CyberWalk: A Web-Based Distributed Virtual Walkthrough Environment, iEEE TRANSACTIONS ON MULTIMEDIA, VOL. 5, NO. 4, DECEMBER 2003, the entire contents of which are incorporated herein by reference) described basic methods of prefetching graphics elements during a walkthrough application. The Cyberwalk system of Chim et al. prefetches graphics objects based on a viewer's proximity to the objects. Chim et al. describe three methods of predicting a user's future location given past current locations. These methods are based on a moving average of past locations and include mean, windowed, and exponential weighted moving averages of past motion vectors. These motion prediction methods do not explicitly take into account limits of velocity or acceleration of viewer motion, nor do they account for navigational restrictions within the environment. Both of these types of limitations could be employed to increase the predictability of navigation and thereby increase the hit rate and/or lower the bandwidth requirement of navigation-based prefetch.
The prefetch method of Chim et al. are based on proximity of the viewer to the graphics objects. As shown in the co-pending PCT patent application number PCT/US2011/042309, visibility is a more efficient basis of navigation-based prefetch than proximity. This is because objects which are in close proximity to a viewer may actually be occluded from the viewer and, conversely, objects that are far from a viewer may be unoccluded. Using visibility instead of proximity as a basis for prefetch requires a practical and precise method of from-region visibility precomputation, which is specified in the co-pending PCT patent application number PCT/US2011/042309.